#include <iostream>
#include <vector>
#include <list>
#include <math.h>
using namespace std;

#include "LRU.h"

struct instruction
{
    int nextInstru;
    instruction(int number) : nextInstru(number + 1) {}
    instruction(int number, int nextNumber) : nextInstru(nextNumber) {}

};

instruction randInstru(int number)
{
    bool isDir = rand() % 2;
    if (number == 0)
        isDir = 1;
    else if (number == 319)
        return instruction(number, rand() % number);

    if (isDir)
    {
        return instruction(number);
    }
    else
    {
        bool front = rand() % 2;
        if (front)
        {
            return instruction(number, rand() % number);
        }
        else
        {
            int nextNum = (rand() % (319 - number + 1)) + number;
            return instruction(number, nextNum);
        }
    }
}

struct instruVec
{
    int pageNum;
    vector<instruction>* page;
};
list<instruVec> allInstruVec;


instruction run(instruction i, LRUCache<int, vector<instruction>*>& LRU, int& miss)
{
    int pageNum = i.nextInstru / 32;
    vector<instruction>* page;
    try
    {
        page = LRU.get(pageNum);
    }
    catch (string)
    {
        miss++;
        LRU.removeHead();
        for (instruVec& ii : allInstruVec)
        {
            if (ii.pageNum == pageNum)
                LRU.push(pageNum, ii.page);
        }
        page = LRU.get(pageNum); //重新run
    }
    return page->at(i.nextInstru % 10);
}


int main()
{
    auto seed = time(0);
    srand(seed);

    int pageNum = 0;
    for (int num = 0; num < 320;)
    {
        vector<instruction>* page = new vector<instruction>;
        for (int i = 0; i < 10; i++, num++)
        {
            page->push_back(randInstru(num));
        }
        allInstruVec.push_back(instruVec{ pageNum,page });
        pageNum++;
    }

    LRUCache<int, vector<instruction>*> LRU(8);
    int i = 0;
    for (instruVec& ii : allInstruVec)
    {
        LRU.push(ii.pageNum, ii.page);
        i++;
        if (i == 8)
            break;
    }

    auto firstPage = LRU.get(0);
    int miss = 0;
    instruction next = run(firstPage->at(0), LRU, miss);
    for (int i = 1; i < 320; i++)
    {
        next = run(next, LRU, miss);
    }
    
    cout << float(miss) / 320 << endl;
    return 0;
}
